{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "
\n", " Hill et claire connu\n", "
\n", "

Navigation dans la page

\n", "

\n", " Si c'est votre première visite dans ce TP, lisez attentivement chacun des points détaillé après ce paragraphe.
\n", " Si vous avez déjà commencer à travailler sur ce TP et que vous souhaiter vous déplacer rapidement dans une partie précise vous pouvez choisir la partie que vous souhaitez rejoindre ci-dessous.
\n", "

\n", " Menu de navigation\n", " \n", "
\n", "

\n", "\n", "
\n", " Technologie jupyter\n", "

\n", " La technologie jupyter permet d'exécuter du code python par un simple clique sur Executer ci-dessus.
\n", " Les morceaux de code de cette page sont interprétées case par case. Pour savoir quelle case a été interprétée avant une autre, il suffit de repérer le numéro devant la case.
\n", " Une fois qu'une case a été interprétée (=exécutée), la page garde en mémoire les variables et fonctions lues
\n", " La plateforme propose quelques outils de purge de la mémoire : \n", "

\n", "

\n", "
\n", "

SAUVEGARDER VOTRE TRAVAIL

\n", "

\n", " Pour ne pas perdre votre travail pensez à le sauvegarder régulièrement. Par défault, la sauvegarde par un clic sur la disquette en haut à gauche de page, ou par le racourci clavier classique ctrl+S\n", " est une sauvegarde en local, sur le serveur de jupyter. Vous pouvez et devez très régulièrement sauvegarder votre travail sur votre support personnel de sauvegarde (clef USB, se l'envoyer par mail etc). Ce faisant vous disposerez d'un fichier .ipynb (IPYthon NoteBook) qu'il vous suffira de recharger pour avancer. Après le rechargement assurez vous que les fonctionnalités anciennement developpées et variables utilisées sont bien dans la mémoire de la page (en rééxecutant les cases, ou plus rapidement par Kernel > Restart & Run All.

\n", "

A NOTER : vous pouvez travailler sur le tp (et tout autre fichier .ipynb) hors connexion en installant une version local du notebook de jupyter. Il faut que votre machine possède un interpreteur de python et que vous soyez connecter à internet.\n", "

    \n", "
  1. Lancer un terminal
    2. \n", "
  2. Taper la commande suivante : pip install jupyterlab
    3. \n", "
  3. Une fois l'installation terminée portez votre attention sur les dernières lignes affichées dans votre terminal vous invitant probablement à taper une ligne de commande pour faire une mise à jour
    4. \n", "
  4. Pour lancer notebook de jupyter, taper dans votre termial : jupyter notebook
    5. \n", "
  5. Votre simulateur de serveur est lancé. Il ne faut pas fermer votre terminal, auquel cas votre simulateur de serveur s'interompera. Suivez le lien indiqué dans les dernières lignes de votre terminal pour vous diriger vers votre espace local. L'interface se présente comme celle que vous trouverez sur le web. Votre travail sera cependant toujours enregistré et jamais perdu même si vous le consultez après plusieurs jours
    6. \n", "
\n", "

\n", "
\n", "
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "

Comme pour le TP1 et le TP2, une bibliothèque regroupant quelques outils de la cryptologie vous ont été donnée. Chargeons l'intégralité des fonctionnalités qu'elle propose

" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "from OutilsCrypto import *" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "

Vous êtes invité à travailler sur la première partie du TP1 pour vous refamiliariser avec les fonctionnalités de cette bibliothèque comme codex, codex, xedoc, paquet, mode2base, Filtre ainsi que les fonctions d'attaque par dictionnaire.

" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "
\n", " Partie 0 : Outils algèbriques\n", "
\n", "\n", "

\n", "

\n", " Menu de navigation\n", " \n", "
\n", "

" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "

Pour vous aider lors de la réalisation de ce TP et des tests de validités, plusieurs fonctionnalité vous ont été donnée. L'objectif de cette partie est de les explorer

" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "

printM(M)

\n", "

Inforamatiquement une matrice sera considéré comme un tableau à deux entrées. Le premier indice correspondera toujours à la ligne tandis que le second à la colonne. On prendra garde, les tableaux sont informatiquement numéroté : le premier indice (ligne ou colonne) a le numéro 0. Par exemple si A est une matrice alors A[0][1] représente la valeur à l'intersection de la première ligne et de la seconde colonne

. \n", "

La procédure printM affiche la matrice passée en paramètre.

" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "M=[[1, 2],[3, 4]]\n", "printM(M)\n", "\n", "N=[[0, -1], [1, 1], [1, 0]]\n", "printM(N)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "

prodMat(A,B)

\n", "

Cette fonction renvoie le résultat du produit matriciel $A\\times B$. En ca d'impossibilité la matrice vide (tableau vide) est renvoyé.

" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "print(\"N*M =\")\n", "printM( prodMat(N, M) )\n", "print(\"M*N =\")\n", "printM( prodMat(M, N) )" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "
\n", " Partie 1 : TP2 - outils arithmétiques\n", "
\n", "\n", "

\n", "

\n", " Menu de navigation\n", " \n", "
\n", "

" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "

Reprennez du TP2, la fonction PGCD qui prend en paramètre deux entiers a et b et qui renvoie le plus grand diviseur commun à ces deux nombres.

" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def PGCD(a, b) :\n", " return 0" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "

Tests

" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "a=10\n", "b=15\n", "print(\"PGCD(\",a,\", \",b,\")=\", PGCD(a, b)) #5\n", "a=100\n", "b=150\n", "print(\"PGCD(\",a,\", \",b,\")=\", PGCD(a, b)) #50\n", "a=1983\n", "b=666\n", "print(\"PGCD(\",a,\", \",b,\")=\", PGCD(a, b)) #3" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "

Reprennez du TP2, la fonction inv_mod qui prend en paramètre deux entiers a et n et renvoie l'inverse de a modulo n. On convient que lorsque c'est impossible, la fonction renvoie $0$

" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def inv_mod(a, n) :\n", " return 0" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "

Tests

" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "a=[19, 11, 876, 1777]\n", "n=[13, 4, 484, 1111]\n", "for i in range(len(a)) :\n", " a1=inv_mod(a[i], n[i])\n", " if(a1==0) : print(a[i], \"n'est pas inversible modulo\", n[i])\n", " else : print(a[i], \"^(-1) modulo\", n[i], \"=\", a1)\n", "#19 ^(-1) modulo 13 = 11\n", "#11 ^(-1) modulo 4 = 3\n", "#876 n'est pas inversible modulo 484\n", "#1777 ^(-1) modulo 1111 = 739" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "
\n", " Partie 2 : Hill en dimension $2$\n", "
\n", "\n", "

\n", "

\n", " Menu de navigation\n", " \n", "
\n", "

" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "

Dans cette partie, comme vu en cours et en TD, nous nous intérèsserons uniquement à l'application du cryptosystème de Hill en dimension 2, c'est à dire que nous ne considèrerons que des matrices à 2 lignes et deux colonnes.

" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "

Ecrire la fonction detDim2 qui prend en paramètre une matrice A et renvoie son déterminant (en suivant simplement ce que nous avions nomé dans le cours la règle du gamma)

" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def detDim2(A) : \n", " return 0" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "

Tests

" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "B=[\n", " [2, 3],\n", " [5, 7]\n", "]\n", "printM(B)\n", "print(\"Le déterminant de cette matrice vaut : \",detDim2(B))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "

Ecrire la fonction inv_mat_modDim2(A, n) qui renvoie l'inverse d'une matrice A (toujours en dimension 2 - en appliquant donc simplement la formule vu en cours) modulo n. En cas d'impoibilité, on renvoie la matrice vide (tableau vide)

" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def inv_mat_modDim2(A, n) :\n", " return A" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "

Tests

" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "print(\"L'inverse de \")\n", "printM(B)\n", "print(\"est\")\n", "printM(inv_mat_modDim2(B, 26))\n", "#19, 3\n", "#5, 24" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "

Ecrire la fonction EHillDim2 qui renvoie le chiffrement de Hill. La fonction renvoie la chaine vide en cas d'erreur.

" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def EHillDim2(txt, A, paq=1) :\n", " return \"\"" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "

Tests

" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "print(EHillDim2(\"QMPPEXZVIKUL\", B))#QIXYZZJMUGVV" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "

Ecrire la fonction DHillDim2 qui renvoie le déchiffrement de Hill. La fonction renvoie la chaine vide en cas d'erreur.

" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def DHillDim2(txt, A, paq=1) :\n", " return \"\"" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "

Tests

" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "print(DHillDim2(\"QMPPEXZVIKUL\", B))" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "txt0=\"COUCOULESETUDIANTSALORSCASEPASSEBIEN\"\n", "txt1=EHillDim2(txt0, B)\n", "txt2=DHillDim2(txt1, B)\n", "print(\"Message initiale :\", txt0)\n", "print(\"Message chiffré :\", txt1)\n", "print(\"Message déchiffré :\", txt2)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "
\n", " Partie 3 : Brute force (dim 2)\n", "
\n", "\n", "

\n", "

\n", " Menu de navigation\n", " \n", "
\n", "

" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "

La fonction suivante, incrémente la matrice A modulairement (mod). Si suite à cet incrément on trouve la matrice nulle on renvoie à la place la matrice vide (tableau vide)

" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def Incr_Mat(A, mod) : \n", " n=len(A)\n", "\n", " i=0\n", " while(iLa case suivante, liste toutes les matrices (en dimension $2$) en binaire.

" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "X=[[0, 0], [0, 0]]\n", "while(len(X)>0) :\n", " X=Incr_Mat(X, 2)\n", " printM(X)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "

Comme pour les TP1 et TP2, rédiger une fonction d'attaque en force brute, utlisant la recherche par dictionnnaire

" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "print(\"-----> DéBUT DU CHARGMENT DES DICTIONNAIRES <-----\")\n", "top=time.time()\n", "lang=\"FR\"\n", "print(\"CHARGEMENT DU DICTIONNAIRE \\\"\", lang, \"\\\": \\tEN COURS\",end='')\n", "DICO_FR = MonDico(lang)\n", "print(\"\\rCHARGEMENT DU DICTIONNAIRE \\\"\", lang, \"\\\": \\tTERMINéE (en\", round(time.time()-top, 3), \"secondes)\")\n", "top=time.time()\n", "lang=\"ANG\"\n", "print(\"CHARGEMENT DU DICTIONNAIRE \\\"\", lang, \"\\\": \\tEN COURS\",end='')\n", "DICO_ANG = MonDico(lang)\n", "print(\"\\rCHARGEMENT DU DICTIONNAIRE \\\"\", lang, \"\\\": \\tTERMINéE (en\", round(time.time()-top, 3), \"secondes)\")\n", "top=time.time()\n", "lang=\"ESP\"\n", "print(\"CHARGEMENT DU DICTIONNAIRE \\\"\", lang, \"\\\": \\tEN COURS\",end='')\n", "DICO_ESP = MonDico(lang)\n", "print(\"\\rCHARGEMENT DU DICTIONNAIRE \\\"\", lang, \"\\\": \\tTERMINéE (en\", round(time.time()-top, 3), \"secondes)\")\n", "top=time.time()\n", "lang=\"IT\"\n", "print(\"CHARGEMENT DU DICTIONNAIRE \\\"\", lang, \"\\\": \\tEN COURS\",end='')\n", "DICO_IT = MonDico(lang)\n", "print(\"\\rCHARGEMENT DU DICTIONNAIRE \\\"\", lang, \"\\\": \\tTERMINéE (en\", round(time.time()-top, 3), \"secondes)\")\n", "print(\"-----> FIN DU CHARGMENT DES DICTIONNAIRES <-----\")" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def bruteforceHill_dico(txt, paq=1, dico=DICO_FR) : \n", " try : \n", " txt=str(txt)\n", " paq=int(paq)\n", " except :\n", " print(\"L'attaque ne fonctionne pas\")\n", " return\n", "\n", " print(\"---------------------------------------------------\")\n", " print(\"Début de l'attaque en force brute avec dictionnaire\")\n", " print(\"---------------------------------------------------\")\n", " \n", " top=time.time()\n", " \n", " #Mettre votre code ici\n", " \n", " temps=time.time()-top\n", " print(\"Le dernier message semble être le bon\")\n", " print(\"Attaque terminée (\"+str(round(temps, 3))+\"s)\")\n", " print(\"---------------------------------\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "

Tests

" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "#par paquet 1 cette attaque dure (sur un core i5) environ 45 secondes\n", "#Vous aventurerez-vous à changer paq en 2 ?\n", "#Aurez-vous la folie de le mettre 3 ?\n", "paq=1\n", "B=[\n", " [2, 3],\n", " [5, 7]\n", "]\n", "txt = \"BONJOURLESETUDIANTSCOMMENTCASEPASSECETTEATTAQUEPASTROPLONGPOINTDINTEROGATION\"\n", "txt2 = EHillDim2(txt, B, paq)\n", "print(\"Attaque du message : \")\n", "print(txt2)\n", "bruteforceHill_dico(txt2, paq)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "
\n", " Partie 4 : Hill en dimension $N$\n", "
\n", "\n", "

\n", "

\n", " Menu de navigation\n", " \n", "
\n", "

" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "

Outils algèbriques : det et inv_mat_mod

" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "

Comme en dimension $2$, il existe des formule bien connue permettant de calculer le determinant de n'importe quelle matrice carré ainsi que son inverse (lorsque son déterminant est inversible). Ce n'est pas l'objectif de ce cours que d'introduie ces notion : elles sont gratuites !\n", "

\n", "

" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "A=[\n", " [1, 3, 3, 7], \n", " [0, 1, 2, 1], \n", " [5, 6, 7, 3], \n", " [9, 1, 0, 3]\n", "]\n", "print(\"A=\")\n", "printM(A)\n", "print(\"det(A)=\", det(A))\n", "print(\"PGCD(det(A), 26)=\", PGCD(det(A), 26))\n", "print(\"A^(-1) =\")\n", "printM(inv_mat_mod(A, inv_mod(det(A), 26), 26))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "

En adaptant votre code en dimension 2, écrire les fonctions EHill et DHill de déchiffrement quelque soit la dimension de la matrice clef.

" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def EHill(txt, A, paq=1) :\n", " return \"\"" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def DHill(txt, A, paq=1) :\n", " return \"\"" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "#Dernier exercice de la feuille de TD\n", "A=[\n", " [8, 3, 0],\n", " [1, 1, 11], \n", " [0, 8, 7]\n", "]\n", "print(DHill(\"YNDKDUUHSLYZGEA\", A))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "
\n", " Partie 5 : Attaque à claire connu\n", "
\n", "\n", "

\n", "

\n", " Menu de navigation\n", " \n", "
\n", "

" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "

On renvoie au cours pour comprendre le principe des associations et les constructions vectoriels qui se déduisent du claire connu ($\\rightarrow$ ici (bas de page)).\n", "
\n", " Le principe est donc d'associer les informations vectoriellement pour obtenir des équations de la forme $AU=V$ où $U$ est une partie claire du message, $V$ une partie crypté du message et $A$ la clef inconnue que nous cherchons à casser. La difficulté de cette attaque est purement algorithmique : il faut créer tous les $U$ et $V$ possible pour obtenir une matrice inversible permettant de trouver $A=VU^{-1}$. A cette fin, nous vous proposons la fonction lst_ss_ens(E, p) qui est un tableau regroupant tous les sous-ensembles (sous tableau) de cardinalité $p$ que l'on peut faire avec le tableau $E$.\n", "

" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "E=['a', 'b', 'c', 'd']\n", "print(lst_ss_ens(E, 2))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "

Ecrire la fonction AttaqueAClaireConnu qui réalise une attaque à claire connue. Quelques petite aides vous sont soufflé.
\n", "A propos des paramètres : \n", "

\n", "Nous ne raisonons que par paquet de 1.\n", "

" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def AttaqueAClaireConnu(crypte, claire, pos=0, dim=2) :\n", "\n", " #il faut que la position (pos) soit le premier coef d'un vecteur\n", " deb=pos\n", " while(deb%dim!=0) : deb+=1\n", " if(deb-pos>len(claire)) :\n", " print(\"Informations insufissantes pour une attaque - I\")\n", " return\n", "\n", " #Il faut que la fin du message soit le dernier coef d'un vecteur\n", " fin=min(len(claire)+pos, len(crypte))\n", " while(fin%dim!=0) : fin-=1\n", "\n", " if(fin<=deb) :\n", " print(\"Informations insufissantes pour une attaque - II\")\n", " return\n", "\n", " return \"\"" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "

Test

" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "#Dernier slide de la présentation du cours\n", "crypte=\"VZRQOOHQEMWIVNDOHZXBRCCGZDBXHOQSKMISXULTTSXFDHNXJSZBEZVEQOXHLPT\"\n", "claire=\"TAIREAUPLUSVITE\"\n", "pos=len(crypte)-len(claire)\n", "AttaqueAClaireConnu(crypte, claire, pos ,3)" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.6.0" } }, "nbformat": 4, "nbformat_minor": 2 }